package com.zjsru.leetcode75.level1;

/**
 * @Author: cookLee
 * @Date: 2023-11-13
 * 打家劫舍
 */
public class Rob {

    /**
     * 主
     * \
     * 输入：[1,2,3,1]
     * 输出：4
     * 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     *      偷窃到的最高金额 = 1 + 3 = 4 。
     *  \
     *  输入：[2,7,9,3,1]
     * 输出：12
     * 解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     *      偷窃到的最高金额 = 2 + 9 + 1 = 12 。
     * @param args args
     */
    public static void main(String[] args) {
        Rob rob = new Rob();
        int[] nums = new int[]{1,2,3,1};
        System.out.println(rob.rob2(nums));
    }

    /**
     * 动态规划
     *
     * @param nums nums
     * @return int
     */
    public int rob(int[] nums) {
        int prev = 0;
        int curr = 0;
        for (int num : nums) {
            int temp = Math.max(curr, prev + num);
            prev = curr;
            curr = temp;
        }
        return curr;
    }

    /**
     * 动态规划
     *
     * @param nums nums
     * @return int
     */
    public int rob2(int[] nums) {
        if(nums.length == 0){
            return 0;
        }
        int[] dp = new int[nums.length + 1];
        dp[0] = 0;
        dp[1] = nums[0];
        for(int i = 2; i <= nums.length; i++){
            int max = Math.max(dp[i - 2] + nums[i - 1], dp[i - 1]);
            dp[i] = max;
        }
        return dp[nums.length];
    }

}
